package _dp

import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/pascals-triangle/description/

118. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:
输入: numRows = 1
输出: [[1]]


提示:
1 <= numRows <= 30
 */
class leetcode_118 {
    /**
     * 题型：动态规划
     *
     * 思路：
     * 规律：
     *
     *            1
     *         1    1
     *      1     2     1
     *
     *   1     3     3     1
     *
     *   数组第初始化 - 第1行和第2行
     *   第1行，1
     *   第2行，1，1
     *
     *   从第3行开始：
     *   row -> [3, numRows]，每行 i -> [0, row)
     *   两边的值:1
     *   非两边的值：当前j行 i 的值 = 上一行(j-1) i的值 + 上一行(j-1) i-1的值
     *   dp[j][i] = dp[j-1][i] + dp[i-1][i-1]
     *
     */

    @Test
    fun test_1() {
        val actual = generate(5)
        val expected = "[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]"
        Assert.assertEquals(expected, actual.toString())
    }

    @Test
    fun test_2() {
        val actual = generate(1)
        val expected = "[[1]]"
        Assert.assertEquals(expected, actual.toString())
    }

    private fun generate(numRows: Int): List<List<Int>> {
        // 1 确定数组以及下标含义
        val dp: ArrayList<ArrayList<Int>> = ArrayList()
        // 2 确定递归公式
        // 3 初始化数组
        val list: ArrayList<Int> = ArrayList()
        list.add(1)
        dp.add(list)

        if (numRows == 1) {
            return dp
        }
        val list2: ArrayList<Int> = ArrayList()
        list2.add(1)
        list2.add(1)
        dp.add(list2)

        if (numRows == 2) {
            return dp
        }
        // 4 遍历顺序
        for (row in 3..numRows) {
            val lastRow: ArrayList<Int> = dp.get(dp.size - 1)
            val list: ArrayList<Int> = ArrayList()
            for (i in 0 until row) {
                if (i == 0 || i == row - 1) {
                    list.add(1)
                } else {
                    list.add(lastRow[i] + lastRow[i - 1])
                }
            }
            // 5 打印数组
            println("row=$row, list=:$list")
            dp.add(list)
        }
        return dp
    }
}